package 力扣_树算法.搜索树;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**98. 验证二叉搜索树
 * @author zx
 * @create 2022-04-15 15:25
 */
public class Num98 {
    /**
     * @return 递归(中序遍历)
     */
    public boolean isValidBST2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        for(int i = 0;i < list.size() - 1;i++){
            if(list.get(i) >= list.get(i + 1)){
                return false;
            }
        }
        return true;
    }
    private void inOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }

    /**
     * @return 迭代(中序遍历)
     */
    public boolean isValidBST(TreeNode root) {
        Double inorder = Double.MIN_VALUE;
        // 因为二叉搜索树的中序遍历结果集是一个升序的;所以可以判断中序遍历的前一个节点
        // 是否小于后一个节点值,进而验证二叉搜索树
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if(node.val <= inorder){
                return false;
            }
            inorder = (double)node.val;
            node = node.right;
        }
        return true;
    }
}
